Search Results

Documents authored by Schleimer, Saul

Document
DOI: 10.4230/DagRep.12.2.17
Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar 22062)

Authors: Maike Buchin, Anna Lubiw, Arnaud de Mesmay, Saul Schleimer, and Florestan Brunck

Published in: Dagstuhl Reports, Volume 12, Issue 2 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22062 "Computation and Reconfiguration in Low-Dimensional Topological Spaces". The seminar consisted of a small collection of introductory talks, an open problem session, and then the seminar participants worked in small groups on problems on reconfiguration within the context of objects as diverse as elimination trees, morphings, curves on surfaces, translation surfaces and Delaunay triangulations.
Cite as

Maike Buchin, Anna Lubiw, Arnaud de Mesmay, Saul Schleimer, and Florestan Brunck. Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar 22062). In Dagstuhl Reports, Volume 12, Issue 2, pp. 17-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{buchin_et_al:DagRep.12.2.17,
  author =	{Buchin, Maike and Lubiw, Anna and de Mesmay, Arnaud and Schleimer, Saul and Brunck, Florestan},
  title =	{{Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar 22062)}},
  pages =	{17--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{2},
  editor =	{Buchin, Maike and Lubiw, Anna and de Mesmay, Arnaud and Schleimer, Saul and Brunck, Florestan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.2.17},
  URN =		{urn:nbn:de:0030-drops-169305},
  doi =		{10.4230/DagRep.12.2.17},
  annote =	{Keywords: Geometric Topology, Computational Geometry, Graph Drawing, Reconfiguration, Dagstuhl Seminar}
}
Document
DOI: 10.4230/DagRep.9.8.84
Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352)

Authors: Maarten Löffler, Anna Lubiw, Saul Schleimer, and Erin Moriarty Wolf Chambers

Published in: Dagstuhl Reports, Volume 9, Issue 8 (2020)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19352 ``Computation in Low-Dimensional Geometry and Topology''. The seminar participants investigated problems in: knot theory, trajectory analysis, algorithmic topology, computational geometry of curves, and graph drawing, with an emphasis on how low-dimensional structures change over time.
Cite as

Maarten Löffler, Anna Lubiw, Saul Schleimer, and Erin Moriarty Wolf Chambers. Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352). In Dagstuhl Reports, Volume 9, Issue 8, pp. 84-112, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{loffler_et_al:DagRep.9.8.84,
  author =	{L\"{o}ffler, Maarten and Lubiw, Anna and Schleimer, Saul and Wolf Chambers, Erin Moriarty},
  title =	{{Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352)}},
  pages =	{84--112},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{8},
  editor =	{L\"{o}ffler, Maarten and Lubiw, Anna and Schleimer, Saul and Wolf Chambers, Erin Moriarty},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.8.84},
  URN =		{urn:nbn:de:0030-drops-117734},
  doi =		{10.4230/DagRep.9.8.84},
  annote =	{Keywords: Geometric topology, Graph Drawing, Computational Geometry}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.37
Compressed Decision Problems in Hyperbolic Groups

Authors: Derek Holt, Markus Lohrey, and Saul Schleimer

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We prove that the compressed word problem and the compressed simultaneous conjugacy problem are solvable in polynomial time in hyperbolic groups. In such problems, group elements are input as words defined by straight-line programs defined over a finite generating set for the group. We prove also that, for any infinite hyperbolic group G, the compressed knapsack problem in G is NP-complete.
Cite as

Derek Holt, Markus Lohrey, and Saul Schleimer. Compressed Decision Problems in Hyperbolic Groups. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{holt_et_al:LIPIcs.STACS.2019.37,
  author =	{Holt, Derek and Lohrey, Markus and Schleimer, Saul},
  title =	{{Compressed Decision Problems in Hyperbolic Groups}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.37},
  URN =		{urn:nbn:de:0030-drops-102766},
  doi =		{10.4230/LIPIcs.STACS.2019.37},
  annote =	{Keywords: hyperbolic groups, algorithms for compressed words, circuit evaluation problems}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact